package com.java.multipledatasource.algorithm;

/**
 * @author hu
 * @version 1.0
 * @date 2021/1/21 00 21 下午 1:31
 * @description 数组实现 堆 （） 如果从下标1 开始 左孩子 2 * i (2  << 1)  2 * i +1 (i << i | 1) 父 i/2 （i >> 1）
 *
 *  大根堆，小根堆
 * */

public class Heap {

    private  int[] arr;

    private int limit;

    private int heapSize = 0;

    public boolean isFull() {
        return heapSize == limit;
    }

    public void push(int value) {
        if (isFull()) {
            throw new RuntimeException("heap is full");
        }
        arr[heapSize] = limit;
        heapInsert(arr, heapSize++);

    }

    /**
     * 弹出最大数，并维持大根堆
     * @return
     */
    public int pop(){
        if (heapSize == 0) {
            throw new RuntimeException("heap is empty");
        }
        int res = arr[0];
        swap(arr, 0 , --heapSize);
        heapIfy(arr, 0, heapSize);
        return res;
    }


    public  void heapSort(int[] arr){
        if (arr.length == 0 || arr.length < 2) {
            return;
        }
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr, i);
//        }
        //优化 时间复杂度 o(N)
        for(int i = arr.length; i > 0; i--){
            heapIfy(arr, i , arr.length);
        }

        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
           heapIfy(arr, 0, heapSize);
           swap(arr, 0, --heapSize);
        }
    }

    private void heapIfy(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;
        int large = 0;
        while (left < heapSize) {

            large = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;

            large = arr[index] > arr[large] ? index : large;

            if (large == index) {
                break;
            }
            swap(arr, large, index);
            index = large;
            left = index * 2 + 1;
        }
    }

    private void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index -1 ) / 2;
        }
    }

    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
